A pseudo-random network mobile automaton with linear growth

Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n) then it settles to a very regular behavior and rate. A pseudo-random mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.     

Robot learning language — Integrating programming and learning for cognitive systems

One central property of cognitive systems is the ability to learn and to improve continually. We present a robot control language that combines programming and learning in order to make learning executable in the normal robot program. The language constructs of our learning language RoLL rely on the concept of hierarchical hybrid automata to enable a declarative, explicit specification of learning problems. Using the example of an autonomous household robot, we point out some instances where learning–and especially continued learning–makes the robot control program more cognitive.     

Tool support for learning Büchi automata and linear temporal logic

We introduce a graphical interactive tool, named GOAL, that can assist the user in understanding Büchi automata, linear temporal logic, and their relation. Büchi automata and linear temporal logic are closely related and have long served as fundamental building blocks of linear-time model checking. Understanding their relation is instrumental in discovering algorithmic solutions to model checking problems or simply in using those solutions, e.g., specifying a temporal property directly by an automaton rather than a temporal formula so that the property can be verified by an algorithm that operates on automata. One main function of the GOAL tool is translation of a temporal formula into an equivalent Büchi automaton that can be further manipulated visually. The user may edit the resulting automaton, attempting to optimize it, or simply run the automaton on some inputs to get a basic understanding of how it operates. GOAL includes a large number of translation algorithms, most of which support past temporal operators. With the option of viewing the intermediate steps of a translation, the user can quickly grasp how a translation algorithm works. The tool also provides various standard operations and tests on Büchi automata, in particular the equivalence test which is essential for checking if a hand-drawn automaton is correct in the sense that it is equivalent to some intended temporal formula or reference automaton. Several use cases are elaborated to show how these GOAL functions may be combined to facilitate the learning and teaching of Büchi automata and linear temporal logic. This work was partially supported by the National Science Council, Taiwan (R.O.C.) under grants NSC94-2213-E-002-089, NSC95-2221-E-002-127, NSC95-3114-P-001-001-Y02 (iCAST 2006), NSC96-3114-P-001-002-Y (iCAST 2007), and NSC97-2221-E-002-074-MY3.     

Development and application of a simulation model for changes in land-use patterns under drought scenarios

In arid and semiarid areas of northern China, one of the most vulnerable regional environments, water resources are a key constraint on socioeconomic development. We constructed a simulation model for land-use patterns under a drought transition (i.e., the increased frequency and duration of drought since the late 1970s in the Yongding River Basin study area) to account for the complexity of both the driving factors behind land-use change and the micro-level changes in land-use patterns. This model was a combination of the “top-down” system dynamics model, the “bottom-up” cellular automaton model, and the artificial neural network model. In this model, we considered the socioeconomic development and water resource restrictions, as well as the balance between the land-use requirements and the land supply. We then verified the model through a case study. The results demonstrated the value of constructing a simulation model driven by water resource constraints under the influence of drought. The spatial distribution of land uses in future scenarios will help support decision-making for sustainable regional development.     

Partial order reduction for state/event LTL with application to component-interaction automata

Software systems assembled from a large number of autonomous components become an interesting target for formal verification due to the issue of correct interplay in component interaction. State/event LTL (Chaki et al. (2004, 2005) [1] and [2]) incorporates both states and events to express important properties of component-based software systems.The main contribution of this paper is a partial order reduction technique for verification of state/event LTL properties. The core of the partial order reduction is a novel notion of stuttering equivalence which we call state/event stuttering equivalence. The positive attribute of the equivalence is that it can be resolved with existing methods for partial order reduction. State/event LTL properties are, in general, not preserved under state/event stuttering equivalence. To this end we define a new logic, called weak state/event LTL, which is invariant under the new equivalence.To bring some evidence of the method’s efficiency, we present some of the results obtained by employing the partial order reduction technique within our tool for verification of component-based systems modelled using the formalism of component-interaction automata (Brim et al. (2005) [3]).     

Urban growth modeling of Kathmandu metropolitan region, Nepal

The complexity of urban system requires integrated tools and techniques to understand the spatial process of urban development and project the future scenarios. This research aims to simulate urban growth patterns in Kathmandu metropolitan region in Nepal. The region, surrounded by complex mountainous terrain, has very limited land resources for new developments. As similar to many cities of the developing world, it has been facing rapid population growth and daunting environmental problems. Three time series land use maps in a fine-scale (30 m resolution), derived from satellite remote sensing, for the last three decades of the 20th century were used to clarify the spatial process of urbanization. Based on the historical experiences of the land use transitions, we adopted weight of evidence method integrated in cellular automata framework for predicting the future spatial patterns of urban growth. We extrapolated urban development patterns to 2010 and 2020 under the current scenario across the metropolitan region. Depending on local characteristics and land cover transition rates, this model produced noticeable spatial pattern of changes in the region. Based on the extrapolated spatial patterns, the urban development in the Kathmandu valley will continue through both in-filling in existing urban areas and outward rapid expansion toward the east and south directions. Overall development will be greatly affected by the existing urban space, transportation network, and topographic complexity.     

Approximating Euclidean circles by neighbourhood sequences in a hexagonal grid

In this paper the nodes of the hexagonal grid are used as points. There are three types of neighbours on this grid, therefore neighbourhood sequences contain values 1, 2, 3. The grid is coordinatized by three coordinates in a symmetric way. Digital circles are classified based on digital distances using neighbourhood sequences. They can be triangle, hexagon, enneagon and dodecagon. Their corners and side-lengths are computed, such as their perimeters and areas. The radius of a digital disk is usually not well-defined, i.e., the same disk can have various radii according to the neighbourhood sequence used. Therefore the non-compactness ratio is used to measure the quality of approximation of the Euclidean circles. The best approximating neighbourhood sequence is presented. It is shown that the approximation can be improved using two neighbourhood sequences in parallel. Comparisons to other approximations are also shown.     

Hardness of preorder checking for basic formalisms

We investigate the complexity of preorder checking when the specification is a flat finite-state system whereas the implementation is either a non-flat finite-state system or a standard timed automaton. In both cases, we show that simulation checking is Exptime-hard, and for the case of a non-flat implementation, the result holds even if there is no synchronization between the parallel components and their alphabets of actions are pairwise disjoint. Moreover, we show that the considered problems become Pspace-complete when the specification is assumed to be deterministic. Additionally, we establish that comparing a synchronous non-flat system with no hiding and a flat system is Pspace-hard for any relation between trace containment and bisimulation equivalence, even if the flat system is assumed to be fixed.     

Quasi-rocking real-time pushdown automata

A pushdown automaton (PDA) is quasi-rocking if it preserves the stack height for no more than a bounded number of consecutive moves. Every PDA can be transformed into an equivalent one that is quasi-rocking and real-time and every finite-turn (one-turn) PDA can be transformed into an equivalent one that is quasi-rocking or real-time. The quasi-rocking [quasi-rocking in the increasing mode, and quasi-rocking in the decreasing mode] real-time restriction in finite-turn (one-turn) PDAs coincides with the double Greibach [reverse Greibach, and Greibach] form in nonterminal-bounded (linear) context-free grammars. This provides complete grammatical characterizations of quasi-rocking and/or real-time (finite-turn and one-turn) PDAs and, together with known relations and other relations proved in the present paper, yields an extended hierarchy of PDA languages. Basic decision properties for PDAs can be stated in stronger forms by using the quasi-rocking and real-time restrictions and their undecidability/decidability status rests on the way PDAs quasi-rock.     

BACH:线性混成系统有界可达性模型检验工具

混成自动机的模型检验问题非常困难,即使是其中相对简单的一个子类--线性混成自动机,它的可达性问题仍然是不可判定的.现有的相关工具大都使用多面体计算来判定线性混成自动机状态空间的可达集,复杂度高、效率低,无法解决实际应用规模的问题.描述了一个面向线性混成系统有界可达性模型检验工具--BACH(bounded reacha...